class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // 把数组当作一个链表来看，数组的下标就是指向元素的指针，把数组的元素也看作指针。
        // 如 0 是指针，指向 nums[0]，而 nums[0] 也是指针，指向 nums[nums[0]].
        // 例如[1,2,3,4,5,6,7,8,9,5]
        // 按照上面的循环下去就会得到这样一个路径：1 2 3 4 5 [6 7 8 9] [6 7 8 9] [6 7 8 9] . . .这样就有了一个环
        // 而 5 就是环的入口点，也是那个重复出现的数

        // 1. 找出在环中相遇的位置
        int slow = 0, fast = 0;
        while(1)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if(slow == fast)
                break;
        }

        // 2. 在环中相遇的位置和起始位置同时走，相遇的位置就是环的入口点
        int ret = 0;
        while(1)
        {
            slow = nums[slow];
            ret = nums[ret];
            if(slow == ret)
                break;
        }
        return ret;

        // 下面这种做法也不行，修改了原数组
        // int n = nums.size();
        // sort(nums.begin(), nums.end());
        // for(int i = 0; i < n; i++)
        // {
        //     if(nums[i] - i == 0)
        //         return nums[i];
        // }
        // return 0;

        // 使用了额外空间，O(N)
        // unordered_set<int> hash;
        // for(auto &x : nums)
        // {
        //     if(!hash.count(x))
        //         hash.insert(x);
        //     else
        //         return x;
        // }
        // return 0;
    }
};